Search for: All records

This paper studies the Heavy Traffic (HT) joint distribution of queue lengths in an Input-queued switch (IQ switch) operating under the MaxWeight scheduling policy. IQ switchserve as representative of SPNs that do not satisfy the socalled Complete Resource Pooling (CRP) condition, and consequently exhibit a multidimensional State Space Collapse (SSC). Except in special cases, only mean queue lengths of such non-CRP systems is known in the literature. In this paper, we develop the Transform method to study the joint distribution of queue lengths in non-CRP systems. The key challenge is in solving an implicit functional equation involving the Laplace transform of the HT limiting distribution. For the general n x n IQ switch that has n2 queues, under a conjecture on uniqueness of the solution of the functional equation, we obtain an exact joint distribution of the HT limiting queue-lengths in terms of a non-linear combination of 2n iid exponentials. 

In general, obtaining the exact steady-state distribution of queue lengths is not feasible. Therefore, we focus on establishing bounds for the tail probabilities of queue lengths. We examine queueing systems under Heavy Traffic (HT) conditions and provide exponentially decaying bounds for the probability P(∈q > x), where ∈ is the HT parameter denoting how far the load is from the maximum allowed load. Our bounds are not limited to asymptotic cases and are applicable even for finite values of ∈, and they get sharper as ∈ - 0. Consequently, we derive non-asymptotic convergence rates for the tail probabilities. Furthermore, our results offer bounds on the exponential rate of decay of the tail, given by -1/2 log P(∈q > x) for any finite value of x. These can be interpreted as non-asymptotic versions of Large Deviation (LD) results. To obtain our results, we use an exponential Lyapunov function to bind the moment-generating function of queue lengths and apply Markov's inequality. We demonstrate our approach by presenting tail bounds for a continuous time Join-the-shortest queue (JSQ) system.